home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 2475 < prev    next >
Encoding:
Internet Message Format  |  1996-08-06  |  1.7 KB
  1. Path: locutus.rchland.ibm.com!usenet
  2. From: pstaite@vnet.ibm.com
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: Finding Permutations....????
  5. Date: 17 Jan 1996 22:04:14 GMT
  6. Organization: IBM OS/2 Device Driver Development  Rochester, MN
  7. Message-ID: <4djrou$1at3@locutus.rchland.ibm.com>
  8. References: <1996Jan16.160018.24583@oasis.enmu.edu>
  9. Reply-To: pstaite@vnet.ibm.com
  10. NNTP-Posting-Host: warpone.rchland.ibm.com
  11. X-Newsreader: IBM NewsReader/2 v1.2
  12.  
  13. In <1996Jan16.160018.24583@oasis.enmu.edu>, reinholj@math.enmu.edu (John Reinhold) writes:
  14. >I am trying to find a good way to find permutations.
  15. >
  16. >I am looking for an algorythm that would help me
  17. >get started, or lead me in the right direction.
  18.  
  19. ..
  20.  
  21. >I would not like a solution, just a lead in the right direction)
  22.  
  23. OK, read the number/symbol objects into some container.
  24.  
  25. Create a container of "position" objects, same length as other 
  26. container.
  27.  
  28. Recursively iterate through the position objects.
  29.  
  30. At each position, iterate through all unused number/symbol objects in 
  31. the other container.  That is, mark one unused one as used, then 
  32. recursively call the next position.  After recursive call, unmark 
  33. current number/symbol, mark next...
  34.  
  35. When at the last position "boink" each position to output the 
  36. number/symbol it has marked as used.
  37.  
  38. Thus, the last position always sees a choice of only one number/symbol. 
  39. The next to last always sees a choice of two, etc.
  40.  
  41. This algorithm works (I coded a simple linked-list implementation to 
  42. test it).  Note the recursion is only as deep as the number of symbols 
  43. so it isn't too bad.  Number of permutations output grows pretty quick 
  44. :-) though...
  45.  
  46.  
  47. Phil Staite, team OS/2
  48. internet: pstaite@vnet.ibm.com  internal: pstaite@rchland
  49.  
  50.